package com.leet.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class FullSquare {
    public int numSquares(int n) {
        // queue
        Queue<Integer> q = new LinkedList<>();
        // hashset,判断是否存在
        Set<Integer> set = new HashSet<>();

        // 初始化
        q.offer(0);
        set.add(0);
        int level = 0;

        while(!q.isEmpty()){
            level++;
            int size = q.size();
            // 遍历每层
            for(int i = 0;i < size; i++){
                Integer head = q.poll();
                // 遍历子层
                for(int j = 1; j*j <= n; j++){
                    int nodeValue = j*j+ head;
                    if(nodeValue == n){
                        return level;
                    }
                    // 超过，返回父亲层
                    if(nodeValue > n) break;
                    // 未超过，且没有经历过，加入下一次遍历的父层
                    if(!set.contains(nodeValue)){
                        q.offer(nodeValue);
                        set.add(nodeValue);
                    }

                }

            }
        }
        return level;

    }
}
